BZOJ 2705 & 2018 蓝桥国赛第六题 (欧拉函数)

Posted on | In , , ,

BZOJ 2705:
$\sum_{i=1}^{n}\gcd(i,n)\ (n\le2^{32})$

2018 蓝桥国赛第六题：
$\sum_{i=1}^{i=n}\sum_{i=1}^{i=n}\gcd (i,j)^2\ (n\le10^7)$

BZOJ 2705

  • 枚举约数，求$phi$即可
  • 注意枚举$i$的时候还有$\frac{n}{i}$
  • 时间复杂度$O(\sqrt{n}·\log n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll ans, n;

ll phi(ll x)
{
    ll ans=x;
    for(ll i=2;i*i<=x;i++){
        if(x&&x%i==0){
            ans=ans/i*(i-1);
            while(x%i==0)
                x/=i;
        }
    }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}

int main()
{
    scanf("%lld", &n);
    int k=int(sqrt(n+0.5));
    for(int i=1;i<=k;i++)
    {
        if(n%i==0)
        {
            ans += i*(phi(n/i));
            if(i*i != n) ans+=n/i * (phi(i));
        }
    }
    printf("%lld\n", ans);
}

2018 蓝桥国赛第六题

  • 显然也是枚举约数，但需要$O(n)$线性筛求出$[1,10^7]$的$phi$
  • 时间复杂度$O(n)$